﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BT_Mang_Nhom13.Library;
using BT_Mang_Nhom13.Checker;

namespace BT_Mang_Nhom13.Sorter
{
    class QuickSorter<T>:MySorter<T> where T:IComparable<T>
    {
        // Sort theo Cay ke thua//////////////////////////////////
        public override T[] Sort(T[] Data, MyComparer<T> Comparer)
        {
            quicksort(Data, Comparer, 0, Data.Length - 1);
            return Data;
        }

        private void quicksort(T[] data, MyComparer<T> Comparer, int l, int r)
        {
            if (l < r)
            {
                //Chia lam 2 day con
                T pivot = data[(l + r) / 2];
                int low = l, high = r;
                while (low < high)
                {
                    while (Comparer.CompareTo(data[low],pivot) < 0) low++;
                    while (Comparer.CompareTo(data[high],pivot) > 0) high--;
                    if (low <= high)
                    {
                        Swap(data,low, high);
                        low++;
                        high--;
                    }
                }


                quicksort(data,Comparer, l, high);
                quicksort(data,Comparer, low, r);
            }
        }



        // Sort theo delegate///////////////////////////////////////////
        public override T[] Sort(T[] Data, Func<T, T, int> Compare)
        {
            return base.Sort(Data, Compare);
        }

        private void quicksort(T[] data, Func<T, T, int> Compare, int l, int r)
        {
            if (l < r)
            {
                //Chia lam 2 day con
                T pivot = data[(l + r) / 2];
                int low = l, high = r;
                while (low < high)
                {
                    while (Compare(data[low], pivot) < 0) low++;
                    while (Compare(data[high], pivot) > 0) high--;
                    if (low <= high)
                    {
                        Swap(data, low, high);
                        low++;
                        high--;
                    }
                }


                quicksort(data, Compare, l, high);
                quicksort(data, Compare, low, r);
            }
        }
    }
}
